#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int x): data(x), next(nullptr) {}
};

struct cmp {
    bool operator()(const Node* a, const Node* b) {
        return a->data > b->data;
    }
};

Node* merge_k_list(vector<Node*>& lists) {
    priority_queue<Node*, vector<Node*>, cmp> pq;

    for (Node* head : lists) {
        if (head) {
            pq.push(head);
        }
    }

    Node cur = Node(0);
    Node* tail = &cur;
    while (!pq.empty()) {
        Node* top = pq.top();
        pq.pop();

        tail->next = top;
        tail = tail->next;

        if (top->next) {
            pq.push(top->next);
        }
    }

    return cur.next;
}